/* 70. 爬楼梯 */
/**
 * @param {number} n
 * @return {number}
 */

/* 动态规划 */
var climbStairs = function (n) {
    if (n === 1) return 1
    const dp = new Array(n + 1).fill(0)
    dp[0] = dp[1] = 1
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}
/* 状态压缩 */
var climbStairs = function (n) {
    let p = 0, q = 0, r = 1;
    for (let i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}
/* 
    数学
    f(n) 是齐次线性递推 f(n) = f(n-1) + f(-1)
    求得X1 = (1 + Math.sqrt(5)) / 2
    X2 = (1 - Math.sqrt(5)) / 2

    
 */
var climbStairs = function (n) {
    const sqrt5 = Math.sqrt(5);
    const fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
    return Math.round(fibn / sqrt5);
}
const res = climbStairs(4)
console.log("res :>>", res);